#include <iostream>
#include <cstdlib>
#include <limits>
#define MIN (std:;numeric_limits<T>::min())

template <typename T>
    class Node
    {
    public:
	T data;
	Node<T>* lc;
	Node<T>* rc;
	Node<T>* parent;
        Node(){parent = lc = rc = NULL};
	Node(T _data);
    };

template <typename T>
Node<T>::Node(T _data)
{
    data = _data;
    parent = lc = rc = NULL;
};

template <typename T>
class BinaryTree
{
private:
    Node<T>* root;
    Node<T>* NIL;
    void inorder_walk(Node<T>* _x) const;
    void release(Node<T>* _x);
    Node<T>* tree_search(Node<T>* _x,T _data);
    void transplant(Node<T>* u, Node<T>* v);
    
public:
    BinaryTree() {NIL = new Node<T>;NIL->data = MIN;root = NIL;};
    BinaryTree(T _data);
    ~BinaryTree();
    void insert(T _data);
    void inorder_walk() const;
    Node<T>* min(Node<T>* _x) const;
    Node<T>* max(Node<T>* _x) const;
    Node<T>* successor(Node<T>* _x) const;
    Node<T>* predecessor(Node<T>* _x) const;
    Node<T>* tree_search(T _data);
    void BSTSORT(T* _A, int n);
    void tree_delete(Node<T>* z);
};
template <typename T>
void BinaryTree<T>::release(Node<T>* _x)
{
    if (_x != NIL)
    {
	release(_x->lc);
	release(_x->rc);
	delete _x;
    }	
};
template <typename T>
BinaryTree<T>::~BinaryTree()
{
    release(root);
};

template <typename T>
Node<T>* BinaryTree<T>::successor(Node<T>* _x) const
{
    Node<T>* x = _x;
    if (x->rc != NIL)
	return min(x->rc);
    Node<T>* y = x->parent;
    while (y != NIL && x == y->rc)
    {
	x = y;
	y = y->parent;
    }
    return y;
};
template <typename T>
Node<T>* BinaryTree<T>::predecessor(Node<T>* _x) const
{
  Node<T>* x = _x;
  if(x->lc != NIL)
      return max(x->lc);
  Node<T>* y = x->parent;
  while(y != NIL && x == y->lc)
  {
     x = y;
     y = y->parent;
  }
  return y;
};

template <typename T>
Node<T>* BinaryTree<T>::min(Node<T>* _x) const
{
    while (_x->lc != NIL)
	_x = _x->lc;
    return _x;
};
template <typename T>
Node<T>* BinaryTree<T>::max(Node<T>* _x) const
{
    while (_x->rc != NIL)
	_x = _x->rc;
    return _x;
};
template <typename T>
void BinaryTree<T>::inorder_walk() const
{
    inorder_walk(root);
    std::cout << std::endl;
};
template <typename T>
void BinaryTree<T>::inorder_walk(Node<T>* _x) const
{
    if (_x != NIL)
    {
	inorder_walk(_x->lc);
	std::cout << _x->data << "  ";
	inorder_walk(_x->rc);
    }
};
template <typename T>
void BinaryTree<T>::insert(T _data)
{
    Node<T>* y = NIL;
    Node<T>* x = root;
    Node<T>* p = new Node<T>(_data);
    while (x != NIL)
    {
	y = x;
	if (p->data  < x->data)
	    x = x->lc;
	else
	    x = x->rc;
    }
    p->parent = y;
    if (y == NIL)
	root = p;
    else if (p->data < y->data)
	y->lc = p;
    else
	y->rc = p;
};

template <typename T>
Node<T>* BinaryTree<T>::tree_search(T _data)
{
  tree_search(root,_data);
}

template <typename T>
Node<T>* BinaryTree<T>::tree_search(Node<T>* _x,T _data)
{
  if(_x == NIL || _data == _x->data)
    return _x;
  if(_data < _x->data)
  return tree_search(_x->lc,_data);
  else
  return tree_search(_x->rc,_data);
}

template <typename T>
void BinaryTree<T>::BSTSORT(T* _A, int n)
{
 BinaryTree<T> A;
 int i;
 for(i=0; i<n; i++)
 A.insert(_A[i]);
 A.inorder_walk();
}



template <typename T>
BinaryTree<T>::BinaryTree(T _data)
{
    NIL = new Node<T>;
    NIL->data = MIN;
    Node<T> *r = new Node<T>;
    r->data = _data;
    r->lc = NIL;
    r->rc = NIL;
    r->parent = NIL;
    root = r;
};

template <typename T>
void BinaryTree<T>::transplant(Node<T>* u, Node<T>* v)
{
   if(u->parent == NIL)
   root = v;
   else if(u == u->parent->lc)
   u->parent->lc = v;
   else u->parent->rc = v;
   if(v != NIL)
   v->parent = u->parent;
}

template <typename T>
void BinaryTree<T>::tree_delete(Node<T>* z)
{
   if(z->lc == NIL)
   transplant(z, z->rc);
   else if(z->rc == NIL)
   tansplant(z, z->lc);
   else
   {
    Node<T>* y;
    y = min(z->rc);
    if(y->parent != z)
    {
      transplant(y, y->rc);
      y->rc = z->rc;
      y->rc->parent = y;
    }
    transplant(z, y);
    y->lc = z->lc;
    y->lc->parent = y;
   }
}








